package alog;

import java.util.*;

public class copy_list {
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;
        RandomListNode(int label) {
            this.label = label;
        }
    }
    public static void main(String[] args) {

    }

    /**
     * 1、链表的拼接
     * 2、随机指针赋值
     * 3、链表的拆分
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null)
            return null;
        RandomListNode cur = pHead;
        while(cur != null){
            RandomListNode cloneNode = new RandomListNode(cur.label);
            RandomListNode next = cur.next;
            cur.next = cloneNode;
            cloneNode.next = next;
            cur = next;
        }
        cur = pHead;
        while (cur != null){
           cur.next.random = cur.random == null ? null : cur.random.next;
           cur = cur.next.next;
        }
        cur = pHead;
        RandomListNode re = cur.next;
        RandomListNode clone = cur.next;
        while (cur != null){
            cur.next = clone.next;
            clone.next = clone.next == null ? null : clone.next.next;
            cur = cur.next;
            clone = clone.next;
        }
        return re;

    }


    public RandomListNode Clone2(RandomListNode pHead) {
        if(pHead == null)
            return null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while(cur != null){
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(pHead);

    }
}
